package com.zlsy.learning.leetcode.simple;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * @author zhouliang
 * @date 2020/03/13
 **/
public class MajorityElement {

    /**
     * 169：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
     *
     * @param args
     */


    public static void main(String[] args) {
//        int[] nums = new int[]{3, 2, 3};
        int[] nums = new int[]{2, 2, 1, 1, 1, 2, 2, 2};
//        int i = majorityElement(nums);
        int i = majorityElementByVotingAlgorithm(nums);
        System.err.println(i);

    }

    /**
     * 执行用时：21 ms
     * 内存消耗：47.3 MB
     * 复杂度分析：
     * 时间复杂度：O（n）
     * 空间复杂度：S（n）
     *
     * @param nums
     * @return
     */
    public static int majorityElement(int[] nums) {

        int cpn = nums.length / 2;

        Map<Integer, Integer> map = new HashMap<>(16);
        for (int num : nums) {
            //nums的长度为n，则运行n次
            map.merge(num, 1, Integer::sum);
        }
        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        for (Map.Entry<Integer, Integer> next : entries) {
            //运行小于n次
            Integer key = next.getKey();
            Integer value = next.getValue();
            if (value > cpn) {
                return key;
            }
        }
        throw new RuntimeException("没有找到对应的值！");
    }


    /**
     *
     * 执行用时：4 ms
     * 内存消耗：45.6 MB
     *
     * 投票选举算法
     *
     * 时间复杂度：O(n)O(n)。Boyer-Moore 算法只对数组进行了一次遍历。
     *
     * 空间复杂度：O(1)O(1)。Boyer-Moore 算法只需要常数级别的额外空间。
     *
     * @param nums
     * @return
     */
    public static int majorityElementByVotingAlgorithm(int[] nums) {
        int count = 0;
        Integer candidate = null;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            //投票为0，发生换届选举
            if (count == 0) {
                candidate = num;
            }
            //如果num等于候选人：candidate name票数加一 ，否则票数减一
            count += (candidate == num) ? 1 : -1;
        }
        //最后还站着的男人就是胜出者
        return candidate;
    }


}
